package game.pathfinder
{
	import game.map.PhysicalMap;
	
	public class AStar
	{
		private var m_open:Vector.<Node>;
		private var m_closed:Vector.<Node>;
		private var m_physicalMap:PhysicalMap;
		private var m_endNode:Node;
		private var m_startNode:Node;
		private var m_path:Vector.<Node>;
//		private var m_heuristic:Function = manhattan;
//		private var m_heuristic:Function = euclidian;
		private var m_heuristic:Function = diagonal;
		private var m_straightCost:Number = 1.0;
		private var m_diagCost:Number = Math.SQRT2;
		
		public function findPath(physicalMap:PhysicalMap, startX:int, startY:int, endX:int, endY:int):Boolean
		{
			this.m_physicalMap = physicalMap;
			this.m_startNode = physicalMap.getNode(startX, startY);
			this.m_endNode = physicalMap.getNode(endX, endY);
			
			this.m_open = new Vector.<Node>();
			this.m_closed = new Vector.<Node>();
			
			this.m_startNode.g = 0;
			this.m_startNode.h = m_heuristic(m_startNode);
			this.m_startNode.f = m_startNode.g + m_startNode.h;
			
			return search();
		}
		
		public function search():Boolean
		{
			var node:Node = m_startNode;
			while (node != m_endNode)
			{
				var startX:int = Math.max(0, node.column - 1);
				var endX:int = Math.min(m_physicalMap.numColumns - 1, node.column + 1);
				
				var startY:int = Math.max(0, node.row - 1);
				var endY:int = Math.min(m_physicalMap.numRows - 1, node.row + 1);
				
				for (var i:int = startX; i <= endX; i++)
				{
					for (var j:int = startY; j <= endY; j++)
					{
						var test:Node = m_physicalMap.getNode(i, j);
						if (test == node || !test.walkable || !m_physicalMap.getNode(node.column, test.row).walkable || !m_physicalMap.getNode(test.column, node.row).walkable)
						{
							continue;
						}
						
						var cost:Number = m_straightCost;
						if (!((node.column == test.column) || (node.row == test.row)))
						{
							cost = m_diagCost;
						}
						var g:Number = node.g + cost * test.costMultiplier;
						var h:Number = m_heuristic(test);
						var f:Number = g + h;
						if (isOpen(test) || isClosed(test))
						{
							if (test.f > f)
							{
								test.f = f;
								test.g = g;
								test.h = h;
								test.parent = node;
							}
						}
						else
						{
							test.f = f;
							test.g = g;
							test.h = h;
							test.parent = node;
							m_open.push(test);
						}
					}
				}
				for (var o:int = 0; o < m_open.length; o++)
				{
				}
				m_closed.push(node);
				if (m_open.length == 0)
				{
					trace("no path found");
					return false
				}
				m_open.sort(Node.compare);
				node = m_open.shift() as Node;
			}
			buildPath();
			return true;
		}
		
		private function buildPath():void
		{
			m_path = new Vector.<Node>();
			var node:Node = m_endNode;
			m_path.push(node);
			while (node != m_startNode)
			{
				node = node.parent;
				m_path.unshift(node);
			}
		}
		
		public function get path():Vector.<Node>
		{
			return m_path;
		}
		
		private function isOpen(node:Node):Boolean
		{
			for (var i:int = 0; i < m_open.length; i++)
			{
				if (m_open[i] == node)
				{
					return true;
				}
			}
			return false;
		}
		
		private function isClosed(node:Node):Boolean
		{
			for (var i:int = 0; i < m_closed.length; i++)
			{
				if (m_closed[i] == node)
				{
					return true;
				}
			}
			return false;
		}
		
		private function manhattan(node:Node):Number
		{
			return Math.abs(node.column - m_endNode.column) * m_straightCost + Math.abs(node.row + m_endNode.row) * m_straightCost;
		}
		
		private function euclidian(node:Node):Number
		{
			var dx:Number = node.column - m_endNode.column;
			var dy:Number = node.row - m_endNode.row;
			return Math.sqrt(dx * dx + dy * dy) * m_straightCost;
		}
		
		private function diagonal(node:Node):Number
		{
			var dx:Number = Math.abs(node.column - m_endNode.column);
			var dy:Number = Math.abs(node.row - m_endNode.row);
			var diag:Number = Math.min(dx, dy);
			var straight:Number = dx + dy;
			return m_diagCost * diag + m_straightCost * (straight - 2 * diag);
		}
		
		public function get visited():Vector.<Node>
		{
			return m_closed.concat(m_open);
		}
	}
}
